class Solution{
public:
  void nextPermutation(vector<int> &nums){

    if(nums.size() < 2){
      return;
    }

    // 检查是否是降序，如果不是就用index记录第一个不是降序的位置
    int index = -1;
    if(judgeDesc(nums, index)){
      reverse(nums.begin(), nums.end());
      return;
    }

    // 从index后面的比nums[index]大的元素中找一个最小的
    int m = nums[index + 1];
    int pos = index + 1;
    for(int i = index + 1; i < nums.size(); ++i){
      if(nums[i] > nums[index] && m > nums[i]){
        m = nums[i];
        pos = i;
      }
    }
    swap(nums[index], nums[pos]);
    sort(nums.begin() + index + 1, nums.end());

    return;

  }

  bool judgeDesc(vector<int> &nums, int &index){

    bool f = true;

    for(int i = nums.size() - 1; i > 0; --i){
      if(nums[i - 1] < nums[i]){
        f = false;
        index = i - 1;
        break;
      }
    }

    return f;

  }

};